package com.czk.tree.binaryTreePractice;

/**
 * @Author:ChenZhangKun
 * @Date: 2021/3/26 9:44
 */
public class BinaryTreeDemoPractice {
}

class Node {
    /**
     * 值
     */
    int val;
    /**
     * 左节点
     */
    Node left;
    /**
     * 右节点
     */
    Node right;

    public Node(int val, Node left, Node right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    /**
     * 删除数值为val的节点
     *
     * @param val
     */
    public void delete(int val) {
        // 左子树删除
        if (this.left != null && this.left.val == val) {
            this.left = null;
            return;
        }
        // 右子树删除
        if (this.right != null && this.right.val == val) {
            this.right = null;
            return;
        }
        // 递归
        if (this.left != null) {
            this.left.delete(val);
        }
        if (this.right != null) {
            this.right.delete(val);
        }
    }

    /**
     * 前序遍历
     */
    public void preOrderTraverse() {
        // 先输出内容
        System.out.println(this.val);
        if (this.left != null) {
            this.left.preOrderTraverse();
        }
        if (this.right != null) {
            this.right.preOrderTraverse();
        }
    }

    /**
     * 中序遍历
     */
    public void inOrderTraverse() {
        if (this.left != null) {
            this.left.inOrderTraverse();
        }
        System.out.println(this.val);
        if (this.right != null) {
            this.right.inOrderTraverse();
        }
    }

    /**
     * 后序遍历
     */
    public void postOrderTraverse() {
        if (this.left != null) {
            this.left.postOrderTraverse();
        }
        if (this.right != null) {
            this.right.postOrderTraverse();
        }
        System.out.println(this.val);
    }

    /**
     * 前序查找
     *
     * @param val
     * @return
     */
    public Node getByPreTraverse(int val) {
        // 先比较
        if (this.val == val) {
            return this;
        }
        // 左边比较
        Node result = null;
        if (this.left != null) {
            result = this.left.getByPreTraverse(val);
        }
        if (result != null) {
            return result;
        }
        if (this.right != null) {
            result = this.right.getByPreTraverse(val);
        }
        if (result != null) {
            return result;
        }
        return null;
    }

    /**
     * 中序遍历查找
     *
     * @param val
     * @return
     */
    public Node getByInOrderTraverse(int val) {
        // 定义接收节点
        Node result = null;
        if (this.left != null) {
            result = this.left.getByInOrderTraverse(val);
        }
        if (result != null) {
            return result;
        }
        // 与当前节点进行比较
        if (this.val == val) {
            return this;
        }
        // 与右边节点进行比较
        if (this.right != null) {
            result = this.right.getByInOrderTraverse(val);
        }
        if (result != null) {
            return result;
        }
        return null;
    }

    /**
     * 后续查找
     *
     * @param val
     * @return
     */
    public Node getByPostTraverse(int val) {
        Node result = null;
        // 先查找前面的
        if (this.left != null) {
            result = this.left.getByPostTraverse(val);
        }
        if (result != null) {
            return result;
        }
        // 在查找后面的
        if (this.right != null) {
            result = this.right.getByPostTraverse(val);
        }
        if (result != null) {
            return result;
        }
        // 进行查找
        if (this.val == val) {
            return this;
        }
        return null;
    }
}
